package com.my.algorithmlearning.entity;

import org.apache.commons.lang3.StringUtils;

import java.util.*;

/**
 * @ClassName TreeNode
 * @Description TreeNode
 * @Author wanghaiwei
 * @Date 2022/11/23 9:47
 */
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode() {}
    public TreeNode(int val) { this.val = val; }
    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public TreeNode(Integer[] valList) {
        if (valList == null || valList[0] == null) {
            return;
        }
        Queue<TreeNode> nodeStack = new ArrayDeque<>();
        this.val = valList[0];
        nodeStack.add(this);
        TreeNode curr = null;
        int i = 1;
        while (!nodeStack.isEmpty() && i < valList.length) {
            curr = nodeStack.remove();
            if (valList[i] != null) {
                TreeNode left = new TreeNode(valList[i]);
                curr.left = left;
                nodeStack.add(left);
            }
            i++;
            if (i < valList.length && valList[i] != null) {
                TreeNode right = new TreeNode(valList[i]);
                curr.right = right;
                nodeStack.add(right);
            }
            i++;
        }
    }

    public static List<Integer> inorderTraversalByIterator(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> traversalStack = new ArrayDeque<>();
        while(true) {
            if(root != null) {
                traversalStack.push(root);
                root = root.left;
            }else if(!traversalStack.isEmpty()){
                root = traversalStack.pop();
                result.add(root.val);
                root = root.right;
            }else {
                break;
            }
        }
        return result;
    }

    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        result.add(root.val);
        result.addAll(preorderTraversal(root.left));
        result.addAll(preorderTraversal(root.right));
        return result;
    }


    public static List<Integer> bfs(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<Integer> list = new LinkedList<Integer>();

        if (root == null)
            return list;
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode t = queue.remove();
            if (t.left != null)
                queue.add(t.left);
            if (t.right != null)
                queue.add(t.right);
            list.add(t.val);
        }
        return list;
    }

    @Override
    public String toString() {
        Queue<TreeNode> queue = new LinkedList<>();
        List<String> list = new LinkedList<>();
        queue.add(this);
        while (!queue.isEmpty()) {
            TreeNode t = queue.remove();
            if (t.left != null)
                queue.add(t.left);
            if (t.right != null)
                queue.add(t.right);
            list.add(String.valueOf(t.val));
        }
        return StringUtils.join(list,',');
    }
}

